#include <algorithm>
#include "common.h"

using namespace std;

namespace {

void reverse(VectorInt &nums, int i, int j) {
    while (i < j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
        i++; j--;
    }
}

void sortCake(VectorInt &cakes, int n, VectorInt &res) {
    if (n == 1) return;

    int index = 0;
    int maxCake = 0;
    for (int i=0; i<n; i++) {
        if (cakes[i] > maxCake) {
            index = i;
            maxCake = cakes[i];
        }
    }

    reverse(cakes, 0, index);
    res.push_back(index + 1);

    reverse(cakes, 0, n - 1);
    res.push_back(n);

    sortCake(cakes, n - 1, res);
}

VectorInt pancakeSort(VectorInt&& A) {
    vector<int> B(A);
    sort(B.begin(), B.end());
    int n = A.size();
    VectorInt res;
    for(int i = n - 1; i > 0; --i){  // i没有必要等于 0，因为后面都排好序了，第一个也就自然排好了
        if(A[i] != B[i]){
            int j = 0;
            // 查找最大的
            for(; j < n; ++j){
                if(A[j] == B[i]) break;
            }
            std::cout << "a1 " << A << std::endl;
            reverse(A.begin(), A.begin()+j+1);
            std::cout << "a2 " << A << std::endl;
            reverse(A.begin(), A.begin()+i+1);
            res.push_back(j+1);
            res.push_back(i+1);
            std::cout << "res " << res << std::endl;
        }
    }
    return res;
}

VectorInt reverseCake(VectorInt &&cakes) {
    VectorInt res;
    sortCake(cakes, cakes.size(), res);
    std::cout << res << std::endl;
    return res;
}

// 两个字符串数字相乘
string multiply(string s1, string s2) {
    int m = s1.size();
    int n = s2.size();

    VectorInt res(m + n, 0);

    for (int i=m-1; i>=0; i--) {
        for (int j=n-1; j>=0; j--) {
            int mul = (s1[i] - '0') * (s2[j] - '0');
            std::cout << s1[i] << "*" << s2[j] << "=" << mul << std::endl;

            // 乘积在res上的索引位置
            int p = i + j;
            int q = i + j + 1;

            int sum = mul + res[q];
            res[q] = sum % 10;
            res[p] += sum / 10;
        }
    }

    // 跳过前缀未使用的0
    int i = 0;
    while (i<res.size() && res[i] == 0) {
        i++;
    }
    string str;
    for (;i<res.size();i++) {
        str.push_back('0' + res[i]);
    }
    return str.size() == 0 ? "0" : str;
}


void Handle() {
    reverseCake({3, 2, 5, 1});

    pancakeSort({3, 2, 5, 1});

    string s1 = "123";
    string s2 = "45";
    string mul = multiply(s1, s2);
    std::cout << s1 << " * " << s2 << " = " << mul << std::endl;
}

}

void HandleReverseCake() {
    Handle();
}
